// 链表算法
#include "./model/linked-list.h"
#include "./model/double-linked-list.h"

/// @brief 链表原地反转（双指针）
/// @param list 待反转链表
void listReverseDoublePointer(LinkedList list)
{
	// 分别为前指针、当前指针、后指针和头指针备份
	LNode *prior = NULL, *pointer = list->next, *after = NULL, *head = list;
	// 解开环
	head->next = NULL;
	while (pointer != NULL)
	{
		// 先保存下一结点
		after = pointer->next;
		// 当前指向前一个
		pointer->next = prior;
		// 前指针和当前指针后移
		prior = pointer;
		pointer = after;
	}
	// 头结点归位
	head->next = prior;
}

/// @brief 链表原地反转（头插法）
/// @param list 待反转链表
void listReverseHeadInsert(LinkedList list)
{
	// 分别表示当前结点指针、头指针备份和当前下一结点指针
	LNode *pointer = list->next, *head = list, *next = NULL;
	// 先把头摘下来
	head->next = NULL;
	// 依次摘取结点进行头插法
	while (pointer != NULL)
	{
		// 先备份下一个结点
		next = pointer->next;
		// 当前结点头插
		pointer->next = head->next;
		head->next = pointer;
		// 准备下一结点
		pointer = next;
	}
}

/// @brief 有序链表递增（非递减）合并，允许重复，使用给定链表的结点空间
/// @param list1 第一个链表（有序递增的）
/// @param list2 第二个链表（有序递增的）
/// @return 返回合并后的有序链表
LinkedList mergeAsc(LinkedList list1, LinkedList list2)
{
	// 初始化结果链表，就使用list1的头
	LinkedList list = list1;
	// 分别表示第一个和第二个链表的指针，下一个备份指针以及合并结果链表的当前指针
	LNode *p1 = list1->next, *p2 = list2->next, *next, *pointer = list;
	while (p1 != NULL && p2 != NULL)
	{
		// p1不大于p2时，把p1所在结点放到结果中，否则把p2所在结点放入结果
		if (p1->data <= p2->data)
		{
			// 先备份下一个
			next = p1->next;
			p1->next = pointer->next;
			pointer->next = p1;
			p1 = next;
		}
		else
		{
			next = p2->next;
			p2->next = pointer->next;
			pointer->next = p2;
			p2 = next;
		}
		pointer = pointer->next;
	}
	// 若还有没有归并完的，则直接接在末尾
	if (p1 != NULL)
	{
		pointer->next = p1;
	}
	if (p2 != NULL)
	{
		pointer->next = p2;
	}
	return list;
}

/// @brief 有序链表递减（非递增）合并，允许重复，使用给定链表的结点空间
/// @param list1 第一个链表（有序递增的）
/// @param list2 第二个链表（有序递增的）
/// @return 返回合并后的有序链表
LinkedList mergeDec(LinkedList list1, LinkedList list2)
{
	LinkedList list = list1;
	// 分别表示第一个和第二个链表的指针，以及每次头插操作时下一个结点的备份指针
	LNode *p1 = list1->next, *p2 = list2->next, *next;
	// 断开头结点
	list->next = NULL;
	while (p1 != NULL && p2 != NULL)
	{
		// 把小的使用头插法放入结果
		if (p1->data <= p2->data)
		{
			// 先备份下一个
			next = p1->next;
			p1->next = list->next;
			list->next = p1;
			p1 = next;
		}
		else
		{
			next = p2->next;
			p2->next = list->next;
			list->next = p2;
			p2 = next;
		}
	}
	// 然后插入没归并完的
	// 注意这里不能直接往末尾接，还是要一个个地头插
	while (p1 != NULL)
	{
		next = p1->next;
		p1->next = list->next;
		list->next = p1;
		p1 = next;
	}
	while (p2 != NULL)
	{
		next = p2->next;
		p2->next = list->next;
		list->next = p2;
		p2 = next;
	}
	return list;
}

/// @brief 求有序链表的差集，差集最终保存在list1中（求仅出现在list1但是不出现在list2的结点）
/// @param list1 第一个链表（有序递增的）
/// @param list2 第二个链表（有序递增的）
void difference(LinkedList list1, LinkedList list2)
{
	// 分别表示第一个和第二个链表的当前结点指针，第一个链表的前一结点备份指针（删除节点用）和删除时释放内存的指针
	LNode *p1 = list1->next, *p2 = list2->next, *prior = list1, *remove;
	while (p1 != NULL && p2 != NULL)
	{
		// 从list1中删除一样的结点
		if (p1->data == p2->data)
		{
			prior->next = p1->next;
			remove = p1;
			p1 = p1->next;
			free(remove);
			continue;
		}
		if (p1->data < p2->data)
		{
			prior = p1;
			p1 = p1->next;
		}
		else
		{
			p2 = p2->next;
		}
	}
}

/// @brief 求两个有序链表交集，使用给定链表的结点空间（同时在list1和list2中出现的元素）
/// @param list1 第一个链表（有序递增的）
/// @param list2 第二个链表（有序递增的）
/// @return 存放交集的链表
LinkedList intersection(LinkedList list1, LinkedList list2)
{
	LinkedList list = list1;
	// 分别表示第一个链表和第二个链表的指针，下一个备份指针以及结果链表当前指针
	LNode *p1 = list1->next, *p2 = list2->next, *next, *pointer = list;
	// 断开头结点
	list->next = NULL;
	while (p1 != NULL && p2 != NULL)
	{
		// 相同结点插入到list尾部，只取list1的
		if (p1->data == p2->data)
		{
			// 先备份下一结点
			next = p1->next;
			p1->next = pointer->next;
			pointer->next = p1;
			p1 = next;
			p2 = p2->next;
			pointer = pointer->next;
			continue;
		}
		if (p1->data < p2->data)
		{
			p1 = p1->next;
		}
		else
		{
			p2 = p2->next;
		}
	}
	return list;
}

/// @brief 判断list1是否是list2的子集
/// @param list1 第一个链表（有序递增的）
/// @param list2 第二个链表（有序递增的）
/// @return list1是否是list2的子集
int isSubCollection(LinkedList list1, LinkedList list2)
{
	// 分别是指向第一个和第二个链表的当前指针
	LNode *p1 = list1->next, *p2 = list2->next;
	while (p1 != NULL && p2 != NULL)
	{
		// 若p1小于p2，则一定不是子集
		if (p1->data < p2->data)
		{
			return 0;
		}
		// 若两者相等则后移
		if (p1->data == p2->data)
		{
			p1 = p1->next;
			p2 = p2->next;
		}
		else
		{
			// 否则就是p1大于p2当前结点，仅后移p2
			p2 = p2->next;
		}
	}
	return 1;
}

/// @brief 求两个无序链表交集（同时在list1和list2中出现的元素）
/// @param list1 第一个链表（无序）
/// @param list2 第二个链表（无序）
/// @return 存放交集的链表
LinkedList intersectionDisorder(LinkedList list1, LinkedList list2)
{
	LinkedList list = (LNode *)malloc(sizeof(LNode));
	list->data = 0;
	list->next = NULL;
	// 分别是指向第一个和第二个链表的当前指针以及结果链表的当前指针用于尾插
	LNode *p1, *p2, *pointer = list;
	// 无序链表主要是使用双重循环
	for (p1 = list1->next; p1 != NULL; p1 = p1->next)
	{
		for (p2 = list2->next; p2 != NULL; p2 = p2->next)
		{
			if (p1->data == p2->data)
			{
				LNode *node = (LNode *)malloc(sizeof(LNode));
				node->data = p1->data;
				node->next = NULL;
				pointer->next = node;
				pointer = pointer->next;
			}
		}
	}
	return list;
}

/// @brief 链表的选择排序（适用于单链表）
/// @param list 传入链表
void listSelectSort(LinkedList list)
{
	int temp;			// 交换值
	LNode *i, *j, *min; // 分别表示两个遍历指针，以及记录每一趟的最小值的指针
	for (i = list->next; i != NULL; i = i->next)
	{
		min = i;
		for (j = i->next; j != NULL; j = j->next)
		{
			if (j->data < min->data)
			{
				min = j;
			}
		}
		// 交换
		if (i != min)
		{
			temp = i->data;
			i->data = min->data;
			min->data = temp;
		}
	}
}

/// @brief 链表的插入排序（适用于双向链表）
/// @param list 双链表指针
void doubleListInsertSort(DoubleLinkedList list)
{
	if (list->next == NULL)
	{
		return;
	}
	// 两个遍历指针
	DLNode *i, *j;
	int temp; // 临时记录值
	for (i = list->next->next; i != NULL; i = i->next)
	{
		// 当前项与其前一项比较
		if (i->data < i->prior->data)
		{
			// 把i结点的值提出来往前插
			temp = i->data;
			for (j = i->prior; j != list && j->data > temp; j = j->prior)
			{
				j->next->data = j->data;
			}
			j->next->data = temp;
		}
	}
}

int main()
{
	int arr[] = {1001, 16, 2, 33, 55, 90, 1, -10, 12, -77, 102, 1};
	LinkedList l = createList(arr, sizeof(arr) / sizeof(int));
	listSelectSort(l);
	DoubleLinkedList dl = createDoubleLinkedList(arr, sizeof(arr) / sizeof(int));
	doubleListInsertSort(dl);
	printList(l);
	printDoubleList(dl);
	return 0;
}